package com.ljy.my_study.leetcode.连接所有点的最小费用;

import com.ljy.my_study.util.ArrayUtil;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/1/19 10:21
 */
public class TestMain {

//    给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
//
//    连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
//
//    请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
//
//             
//
//    示例 1：
//
//
//
//    输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
//    输出：20
//    解释：
//
//    我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
//    注意到任意两个点之间只有唯一一条路径互相到达。
//    示例 2：
//
//    输入：points = [[3,12],[-2,5],[-4,1]]
//    输出：18
//    示例 3：
//
//    输入：points = [[0,0],[1,1],[1,0],[-1,1]]
//    输出：4
//    示例 4：
//
//    输入：points = [[-1000000,-1000000],[1000000,1000000]]
//    输出：4000000
//    示例 5：
//
//    输入：points = [[0,0]]
//    输出：0
//             
//
//    提示：
//
//            1 <= points.length <= 1000
//            -106 <= xi, yi <= 106
//    所有点 (xi, yi) 两两不同。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
//        int[][] points=ArrayUtil.changeStr2Array("[[15,14],[-7,-1],[-19,16],[5,-6],[-14,18],[-10,0],[17,-1],[-4,4],[-15,14],[15,-8]]");
//        int[][] points=ArrayUtil.changeStr2Array("[[3,12],[-2,5],[-4,1]]");
        int[][] points=ArrayUtil.changeStr2Array("[[0,0],[2,2],[3,10],[5,2],[7,0]]");
        TestMain testMain=new TestMain();
        Solution solution=new Solution();
        System.out.println(testMain.minCostConnectPoints(points));
        System.out.println(solution.minCostConnectPoints(points));
    }

//  使用并查集

    public int minCostConnectPoints(int[][] points) {
        int len=points.length;
        UnionFind unionFind=new UnionFind(len);
        List<Side> sides=new ArrayList<>();
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                sides.add(new Side(i,j,connectSideValue(points[i],points[j])));
            }
        }
        Collections.sort(sides,(a,b)->a.value-b.value);
        int result=0;
        int num=1;
        for(int i=0;i<sides.size();i++){
            Side side=sides.get(i);
            if(unionFind.union(side.x,side.y)){
                result+=side.value;
                num++;
                if(num==len){
                    break;
                }
            }
        }
        return result;
    }


    private int connectSideValue(int[] pointOne,int[] pointTwo){
        return Math.abs(pointOne[0]-pointTwo[0])+Math.abs(pointOne[1]-pointTwo[1]);
    }
}

class UnionFind{

    int count;
    int[] id;
    int[] size;

    public UnionFind(int count) {
        this.count = count;
        this.id=new int[count];
        this.size=new int[count];
        for(int i=0;i<count;i++){
            this.id[i]=i;
            this.size[i]=1;
        }
    }

    public int find(int index){
        if(index!=id[index]){
            id[index]=find(id[index]);
        }
        return id[index];
    }

    public boolean union(int x,int y){
        int one=find(x);
        int two=find(y);
        if(one==two){
            return false;
        }
        if(size[one]<size[two]){
            int tmp=one;
            one=two;
            two=tmp;
        }
        size[one]+=size[two];
        id[two]=one;
        return true;
    }
}

class Side{
    int x;
    int y;
    int value;

    public Side(int x,int y,int value) {
        this.x=x;
        this.y=y;
        this.value=value;
    }
}
